//编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 
//
// 
// 每行中的整数从左到右按升序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 100 
// -10⁴ <= matrix[i][j], target <= 10⁴ 
// 
// Related Topics 数组 二分查找 矩阵 👍 712 👎 0


package com.cjl.leetcode.editor.cn;
/**
 * [P74]_搜索二维矩阵
 * @author cjl
 * @date 2022-09-11 21:47:24
 */
public class P74_SearchA2dMatrix{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P74_SearchA2dMatrix().new Solution();
          int[][] matrix = new int[][]{
                  {1,2,3},{5,8,9}
          };
           solution.searchMatrix(matrix, 7);
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
          /**
           * 解题思路：每行第一个元素二分查找，确定某行后，再列上二分查询
           * @param matrix
           * @param target
           * @return
           */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(target < matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]){
            return false;
        }
        return rowErfen(matrix, target, 0, matrix.length -1);
    }

    public boolean rowErfen(int[][] matrix, int target, int start , int end){
        if(matrix[end][0] <= target){
            return colErfen(matrix[end], target, 0, matrix[end].length -1);
        }else if(end - start == 1){
            return colErfen(matrix[start], target, 0, matrix[start].length -1 );
        }else if(target >= matrix[(end + start)/2][0]){
            return rowErfen(matrix, target, (end + start) /2, end);
        }else {
            return rowErfen(matrix, target, start, (end + start) /2);
        }
    }
    public boolean colErfen(int[] colmatrix, int target, int start, int end){
        if (start <= end){
            int mid = (start + end) /2 ;
            if(colmatrix[mid] == target || colmatrix[end] == target || colmatrix[start] == target){
                return true;
            }
            if(colmatrix[mid] > target){
                return colErfen(colmatrix, target, start, mid -1);
            }else {
                return colErfen(colmatrix, target, mid + 1, end);
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

  }